/*
 * @Author: 0x9DEFA478
 * @Date: 2025-07-09 20:21:56
 * @LastEditTime: 2025-09-13 17:05:57
 * @LastEditors: 0x9DEFA478
 * @Description: 
 * 
 */
#ifndef hTree_H_Tree_RedBlack_H_
#define hTree_H_Tree_RedBlack_H_
#include "H_Type.h"
#include "./H_Tree.h"
#ifdef __cplusplus
extern "C"{
#endif


typedef struct{
  H_TreeNode Node;
  int IsRed;
}H_TreeNode_RedBlack;

typedef int (*H_TreeNode_RedBlack_CompareKey)(const H_TreeNode_RedBlack*,const void*);


#define H_TreeNode_To_H_TreeNode_RedBlack(in_Node)                cH_GetParentPointer(in_Node,H_TreeNode_RedBlack,Node)


/**
 * @brief 查找节点
 *        虽然是内联函数，但是额外的函数指针可能会拖慢比较操作(例如键为普通的整形时, 影响就会变得非常明显); 在性能场景, 使用该函数不是一个好选择, 建议根据实际场景编写一个优化的实现
 * @param Tree 要查找的树 实际上是树的根节点
 * @param v 指向要查找的Key
 * @param CompareKey 节点与键的比较函数
 * @return 如果不为为NULL则代表查找到的节点 否则代表没有该节点
 */
static inline H_TreeNode_RedBlack* H_Tree_RedBlack_Find(H_TreeNode_RedBlack* Tree,const void* v,H_TreeNode_RedBlack_CompareKey CompareKey){
  H_TreeNode* r;

  r=&Tree->Node;

  while(r!=NULL){
    int res;
    H_TreeNode_RedBlack* i_node;

    i_node=H_TreeNode_To_H_TreeNode_RedBlack(r);

    res=CompareKey(i_node,v);

    if(res==0){
      return i_node;
    }
    if(res<0){
      r=r->Right;
      continue;
    }
    r=r->Left;
  }

  return NULL;
}

/**
 * @brief 查找插入的位置
 *        虽然是内联函数，但是额外的函数指针可能会拖慢比较操作(例如键为普通的整形时, 影响就会变得非常明显); 在性能场景, 使用该函数不是一个好选择, 建议根据实际场景编写一个优化的实现
 * @param Tree 要插入的树 实际上是树的根节点
 * @param v 要插入的Key
 * @param ReturnNode 根据返回值, 有不同的意义
 *        vH_Tree_FindInsert_Result_InsertToLeft或vH_Tree_FindInsert_Result_InsertToRight: 要插入到的父节点
 *        vH_Tree_FindInsert_Result_InsertToRoot: NULL
 *        vH_Tree_FindInsert_Result_Exist: 树内冲突的节点
 * @param CompareKey 节点与键的比较函数
 * @return vH_Tree_FindInsert_Result_
 */
static inline int H_Tree_RedBlack_FindInsert(H_TreeNode_RedBlack* Tree,const void* v,H_TreeNode_RedBlack** ReturnNode,H_TreeNode_RedBlack_CompareKey CompareKey){
  H_TreeNode* Parent;
  int r;

  Parent=&Tree->Node;

  r=vH_Tree_FindInsert_Result_InsertToRoot;

  if(Parent==NULL){
    *ReturnNode=NULL;
    return r;
  }

  for(;;){
    H_TreeNode* Next;
    H_TreeNode_RedBlack* parent;
    int res;

    parent=H_TreeNode_To_H_TreeNode_RedBlack(Parent);
    res=CompareKey(parent,v);

    if(res==0){
      *ReturnNode=parent;
      return vH_Tree_FindInsert_Result_Exist;
    }

    if(res<0){
      Next=Parent->Right;
      if(Next==NULL){
        *ReturnNode=parent;
        r=vH_Tree_FindInsert_Result_InsertToRight;
        break;
      }
    }else{
      Next=Parent->Left;
      if(Next==NULL){
        *ReturnNode=parent;
        r=vH_Tree_FindInsert_Result_InsertToLeft;
        break;
      }
    }
    
    Parent=Next;
  }

  return r;
}

/**
 * @brief 复制节点信息 对于RedBlack树为节点颜色
 * @param Node 节点
 * @param SrcNode 数据源节点
 * @return 无
 */
static inline void H_Tree_RedBlack_Node_Copy(H_TreeNode_RedBlack* Node,const H_TreeNode_RedBlack* SrcNode){
  Node->IsRed=SrcNode->IsRed;
}

/**
 * @brief 查找值最小的节点
 * @param Tree 要查找的树 实际上是树的根节点
 * @return 找到的节点
 */
static inline H_TreeNode_RedBlack* H_Tree_RedBlack_FrontNode(H_TreeNode_RedBlack* Tree){
  H_TreeNode* Front;

  Front=H_Tree_FrontNode(&Tree->Node);
  if(Front==NULL){
    return NULL;
  }
  return H_TreeNode_To_H_TreeNode_RedBlack(Front);
}

/**
 * @brief 查找值最大的节点
 * @param Tree 要查找的树 实际上是树的根节点
 * @return 找到的节点
 */
static inline H_TreeNode_RedBlack* H_Tree_RedBlack_BackNode(H_TreeNode_RedBlack* Tree){
  H_TreeNode* Back;

  Back=H_Tree_BackNode(&Tree->Node);
  if(Back==NULL){
    return NULL;
  }
  return H_TreeNode_To_H_TreeNode_RedBlack(Back);
}

/**
 * @brief 查找下一个节点
 * @param Node 当前节点
 * @return 下一个节点
 */
static inline H_TreeNode_RedBlack* H_Tree_RedBlack_Forward(H_TreeNode_RedBlack* Node){
  H_TreeNode* Forward;

  Forward=H_Tree_Forward(&Node->Node);
  if(Forward==NULL){
    return NULL;
  }
  return H_TreeNode_To_H_TreeNode_RedBlack(Forward);
}

/**
 * @brief 查找上一个节点
 * @param Node 当前节点
 * @return 上一个节点
 */
static inline H_TreeNode_RedBlack* H_Tree_RedBlack_Backward(H_TreeNode_RedBlack* Node){
  H_TreeNode* Backward;

  Backward=H_Tree_Backward(&Node->Node);
  if(Backward==NULL){
    return NULL;
  }
  return H_TreeNode_To_H_TreeNode_RedBlack(Backward);
}

/**
 * @brief 当要释放一个树的内存时, 该函数查找应该处理的第一个节点
 * @param Tree 要查找的树 实际上是树的根节点
 * @return 找到的节点, 返回的节点的子节点至多只有一级(没有孙节点),有两种情况:
 *         1. 返回值是根节点, 这个时候需要释放根节点以及可能存在的左右节点
 *         2. 返回值不是根节点, 这个时候需要释放可能存在的左右节点，返回的节点传入H_Tree_RedBlack_NextFree查找下一个
 */
static inline H_TreeNode_RedBlack* H_Tree_RedBlack_FirstFree(H_TreeNode_RedBlack* Tree){
  H_TreeNode* FirstFree;

  FirstFree=H_Tree_FirstFree(&Tree->Node);
  if(FirstFree==NULL){
    return NULL;
  }
  return H_TreeNode_To_H_TreeNode_RedBlack(FirstFree);
}

/**
 * @brief 当要释放一个树的内存时, 该函数查找应该处理的下一个节点
 *        注意: 该函数会将Node的左右子节点指针设置为NULL, 因为此时左右节点应当被释放
 * @param Node 当前节点
 * @return 返回值说明与H_Tree_RedBlack_FirstFree的相同
 */
static inline H_TreeNode_RedBlack* H_Tree_RedBlack_NextFree(H_TreeNode_RedBlack* Node){
  H_TreeNode* NextFree;

  NextFree=H_Tree_NextFree(&Node->Node);
  if(NextFree==NULL){
    return NULL;
  }
  return H_TreeNode_To_H_TreeNode_RedBlack(NextFree);
}

/**
 * @brief 插入节点到H_Tree_RedBlack_FindInsert查找到的位置
 * @param Tree 要插入的树 实际上是指向树的根节点的指针
 * @param Node 要插入的节点
 * @param ReturnNode 要插入到的父节点 H_Tree_RedBlack_FindInsert返回的节点
 * @param FindInsert_Result H_Tree_RedBlack_FindInsert的返回值 代表要如何插入节点
 * @return 无
 */
void H_Tree_RedBlack_InsertTo(H_TreeNode_RedBlack** Tree,H_TreeNode_RedBlack* Node,H_TreeNode_RedBlack* ReturnNode,int FindInsert_Result);

/**
 * @brief 移除节点
 * @param Tree 要移除节点的树 实际上是指向树的根节点的指针
 * @param Node 要移除的节点 必须保证该节点在树中 否则结果不可预知。
 * @return 无
 */
void H_Tree_RedBlack_Remove(H_TreeNode_RedBlack** Tree,H_TreeNode_RedBlack* Node);


#ifdef __cplusplus
}
#endif
#endif //hTree_H_Tree_RedBlack_H_
